package com.fr.lintcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

public class Q386ii {


    /**
     * @param s: A string
     * @param k: An integer
     * @return: An integer
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        // write your code here
    	if (s == null || s.length() == 0 || k <= 0) {
    		return 0;
    	}
    	int max =  1;
    	//记录字符最后出现的位置
    	for(int i = 0; i < s.length() ; i ++) {
    		Set<Character> set = new HashSet<>();
    		for(int j = i;j < s.length() ; j++) {
    			set.add(s.charAt(j));
    			if(set.size() > k) {
    				max = Math.max(max, j - i);
    				break;
    			}
    		}
    		if(set.size() <= k) {
    			max = Math.max(max, s.length() - i);
    		}
    	}
    	return max;
    }
//    public int lengthOfLongestSubstringKDistinct(String s, int k) {
//    	if (s == null || s.length() == 0 || k == 0) {
//            return 0;
//        }
//
//        int j = 0;
//        int maxLength = 0;
//        Map<Character, Integer> hash = new HashMap<>();
//        for (int i = 0; i < s.length(); i++) {
//            while (j < s.length() && hash.size() <= k) {
//                if (hash.size() == k && !hash.containsKey(s.charAt(j))) {
//                    break;
//                }
//                hash.put(s.charAt(j), hash.getOrDefault(s.charAt(j), 0) + 1);
//                j++;
//            }
//
//            maxLength = Math.max(maxLength, j - i);
//
//            int currentCount = hash.get(s.charAt(i)) - 1;
//            if (currentCount == 0) {
//                hash.remove(s.charAt(i));
//            } else {
//                hash.put(s.charAt(i), currentCount);
//            }
//        }
//        return maxLength;
//    }
    

    
    @Test  
    public void testA() {
    	System.out.println(lengthOfLongestSubstringKDistinct("eceba", 3));
    }

}
